#include<stdio.h>
#include<stdlib.h>
// 链表的入口是指针

typedef struct ListNode
{
    int val;
    struct ListNode *next;    
}ListNode;

// 创建新节点
ListNode *NewNode(int val)
{
    ListNode *p = (ListNode *)malloc(sizeof(ListNode));
    p->val = val;
    p->next = NULL;
    return p;
}
// 输出链表
void print_link(ListNode *head)
{
    while (head!=NULL)
    {
        printf("%d->", head->val);
        head = head->next;
    }
    printf("\n");
}
// 插入节点，不能插入在头节点前面
ListNode *insert(ListNode *p, ListNode *p_front)
{
    if (p_front->next == NULL)
    {
        p_front->next = p;
        p->next = NULL;
    }else {
        p->next = p_front->next;
        p_front->next = p;
    }
}
// 删除节点
void delete_node(ListNode *pos_front)
{
    // 问题情况——pos_front是尾节点
    if(!pos_front->next)
        return;

    ListNode *p = pos_front->next;
    pos_front->next = pos_front->next->next;
    // 释放空间
    free(p);
}
// 访问的是节点，所以返回节点
ListNode *access(ListNode *head, int index)
{
    for (int i = 0; i < index; i++)
    {
        // 超过索引情况
        if (!head)
        {
            return NULL;
        }
        head = head->next;
    }
    return head;
}
// 查找节点，返回索引
int find(ListNode *p, int targe)
{
    int idx = 0;
    while (p->next)
    {
        if (p->val == targe)
        {
            return idx;
        }
        p = p->next;
        idx++;
    }
    // 没找到
    return -1;
}

int main()
{
    // 初始化链表 1 -> 3 -> 2 -> 5 -> 4 
    ListNode *n0 = NewNode(1);
    ListNode *n1 = NewNode(3);
    ListNode *n2 = NewNode(2);
    ListNode *n3 = NewNode(5);
    ListNode *n4 = NewNode(4);
    n0->next = n1;
    n1->next = n2;
    n2->next = n3;
    n3->next = n4; 

    // 输出链表
    ListNode *p = n0;
    print_link(p);

    // 插入节点ni
    ListNode *ni = NewNode(99);
    insert(ni, n3);
    print_link(p);

    // 删除ni
    ListNode *p_front;
    p_front = n3;
    delete_node(p_front);
    print_link(p);

    // 访问索引为2的节点
    ListNode *acc_node = access(p, 2);
    printf("访问的值%d,地址%d\n", acc_node->val, acc_node);

    // 查询值为5的节点
    acc_node = access(p,find(p,5));
    printf("查询的值%d,地址%d\n", acc_node->val, acc_node);
}
